Computer networks are typically comprised of a plurality of communicatively interconnected components. Abstract entities called nodes represent these components within the computer network. In typical operation, one node communicates data and/or information requests in message packets to another node.
In certain circumstances, however, it is desirable for a node to send message packets to more than one other node. Such distribution of message packets to multiple nodes is called multicasting. Various multicast protocols have been devised to govern multicast transmission.
Communication connections between nodes in a computer network are configurable in a wide variety of graph topologies. One common topology is illustrated as a point-to-multipoint star. Similar to a satellite network, nodes in this configuration send and receive message packets through a shared point or "satellite." A common implementation of this graph is to assign a computer network address that more than one, or all, nodes accept as their own. To multicast a message packet, a node addresses the message packet to the common network address and forwards the message packet through the "satellite" for distribution to all of the other nodes.
A disadvantage of such message packet distribution arises when a message packet is addressed to a single node or group of nodes fewer than all nodes in the network. Due to the network's configuration, the message packet is distributed to all nodes in the network. Each node must then process the message packet and filter it out once it discovers the message packet is not addressed to the node. In this manner, a message packet addressed to a single node or group of nodes places a processing burden on every node in the network.
A second common graph topology is a hybrid linear network. Viewing nodes as dots on a page, this topology appears as a "connect-the-dots" configuration. Each node in the network has a communication connection with its neighboring nodes. However, in a computer network having such a configuration, multicasting has certain challenges. A message packet sent from one node to all of its neighboring nodes for forwarding to all of their respective neighboring nodes, etc., would allow the message packet to be distributed to all nodes in the computer network. However, message packet distribution has to be carefully coordinated so that a message packet is not sent back to a node that had already sent it before. If such a situation arose, a message packet could be sent from node to node in a loop without end.
A common solution to eliminate loops in a distribution graph is to set up a spanning tree. A spanning tree is a special type of distribution graph that includes every node in a computer network but contains no loops. For multicasting in such a configuration, a node in a spanning tree sends a message packet to all of its neighboring nodes except the node from which the packet was received. Those neighboring nodes then send a copy of the message packet to all of their respective neighboring nodes except for the sending node. This process is repeated until all of the nodes in the network receive the message packet.
Nevertheless, packet distribution with a spanning tree graph still has disadvantages, particularly when a message packet is addressed to a single node or group of nodes and not the entire network. Sending a message packet to a single node or group of nodes still requires sending the message packet to every node in the network. Consequently, each node in the network must process the message packet. The nodes not addressed in the message packet will route the packet to their respective neighboring nodes without keeping a copy of the packet for themselves because they recognize they are not part of the group to which the message was sent.
The inefficiencies of routing schemes according to these distribution graphs are readily apparent in that each node in the entire network receives and processes each message packet sent over the computer network, whether or not the node is an intended recipient of the message packet. Accordingly, it is desirable to have a distribution graphs for message packets in which nodes that are not addressed in a message packet are limited or eliminated from the resulting routing scheme.